package labuladong;

public class ErFen {

    //  CKG TODO 2023/6/4: 寻找一个数
    int  binarySearch(int[]  nums,int target){
        int left=0;
        int  right=nums.length-1;

        while (left<=right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                return mid;
            } else if (nums[mid]<target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid-1;
            }
        }
    //  CKG TODO 2023/6/4: 这种情况直接返回　－１
        return -1;
    }


    int  binarySearch1(int[]  nums,int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        //  CKG TODO 2023/6/4: 这种写边界条件的　　ｗｈｉｌｅ循环终止的条件是　
        //  CKG TODO 2023/6/4:  left=right 这时候就会缺少一种考虑的情况就是ｌｅｆｔ处的数值判断与ｔａｒｇｅｔ的比较 所以最后要这么写
        return nums[left] == target ? left : -1;
    }

    //  CKG TODO 2023/6/4: 寻找左侧边界的二分搜索

    int binarySearch2(int[] nums,int target){
        int left=0;
        int right=nums.length;
        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                right=mid;        //  CKG TODO 2023/6/4:  此处同下方一样
            }else if (nums[mid]<target){
                left=mid+1;
            }else if (nums[mid]>target){
                //  CKG TODO 2023/6/4:  这一块会打嗝　 因为是左闭右开的区间所以　所以右边的数值要取等于ｍｉｄ　　这样才不会缺少数字没有讨论
                right=mid;
            }
        }
        if (left>=nums.length||nums[left]!=target){
            return -1;
        }
        return  left;
        //  CKG TODO 2023/6/4: 此处为什么没有返回－１　因为既然是搜索左边界呢　说明数组里面一定含有目标数值　　不用返回－１　　　暂且这么理解　－－－－－
    }


    int binarySearch3(int[] nums,int target){
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                right=mid-1;        //  CKG TODO 2023/6/4:  此处同下方一样
            }else if (nums[mid]<target){
                left=mid+1;
            }else if (nums[mid]>target){
                //  CKG TODO 2023/6/4:  这一块会打嗝　 因为是左闭右开的区间所以　所以右边的数值要取等于ｍｉｄ　　这样才不会缺少数字没有讨论
                right=mid-1;
            }
        }

        if (left>=nums.length||nums[left]!=target){
            return -1;
        }
        return  left;
        //  CKG TODO 2023/6/4: 此处为什么没有返回－１　因为既然是搜索左边界呢　说明数组里面一定含有目标数值　　不用返回－１　　　暂且这么理解　－－－－－
    }


    int binarySearch4(int[] nums,int target){
        if (nums.length==0){
            return  -1;
        }
        int left=0;
        int right=nums.length;

        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid;
            }else  if (nums[mid]<target){
                left=mid+1;
            }

        }
        if (left==0){
            return -1;
        }

        return nums[left-1] == target ? left-1 : -1;

    }

    int binarySearch5(int[] nums,int target){
        if (nums.length==0){
            return  -1;
        }
        int left=0;
        int right=nums.length-1;

        while (left<=right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid-1;
            }else  if (nums[mid]<target){
                left=mid+1;
            }

        }
        if (left==0){
            return -1;
        }

        return nums[left-1] == target ? left-1 : -1;

    }
    int binarySearch6(int[] nums,int target){
        if (nums.length==0){
            return  -1;
        }
        int left=0;
        int right=nums.length;

        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid;
            }else  if (nums[mid]<target){
                left=mid+1;
            }

        }
        if (left==0){
            return -1;
        }

        return nums[left-1] == target ? left-1 : -1;

    }


    public static void main(String[] args) {
        ErFen erFen = new ErFen();
        int[]  arr={1,2,2,4};
        System.out.println(erFen.binarySearch6(arr, 2));
    }

}
